#include <stdio.h>
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
//冒泡排序  优化版
int bubble(int a[], int lo, int hi){
	int last = lo;
	while(++lo < hi){
		if (a[lo-1]> a[lo]){
			last = lo;
			swap(a[lo-1],a[ lo]);
		}
	}
	return last;
}


void bubbleSort(int a[], int lo, int hi){
	while (lo < (hi = bubble(a, lo, hi)));
}


int main(){
	int a[] = { 1, 2, 6, 4, 5, 7, 8, 43, 23, 45, 4 };
	int n = sizeof(a) / sizeof(*a);
	bubbleSort(a, 0, n);
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

